package List;

import java.util.HashMap;
import java.util.Map;

public class copyRandomList {
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    /**
     * hot100一刷
     */
    class Solution {
        private Map<Node, Node> visited = new HashMap<>();

        public Node copyRandomList(Node head) {
            if (head == null) {
                return null;
            }

            // 如果已经复制过该节点，直接返回
            if (visited.containsKey(head)) {
                return visited.get(head);
            }

            // 否则，新建一个节点，存入 map
            Node newNode = new Node(head.val);
            visited.put(head, newNode);

            // 递归处理 next、random
            newNode.next = copyRandomList(head.next);
            newNode.random = copyRandomList(head.random);

            return newNode;
        }
    }

    /**
     * hot100二刷
     */
    class Solution1 {
        Map<Node, Node> map = new HashMap<>();

        public Node copyRandomList(Node head) {
            if (head == null)
                return null;
            if (map.containsKey(head)) {
                return map.get(head);
            }
            Node h = new Node(head.val);
            map.put(head, h);
            h.next = copyRandomList(head.next);
            h.random = copyRandomList(head.random);
            return h;
        }
    }
}
